package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.NAryTree.Node;

public class NAryTreeLevelOrderTraversal {
	
	//方法一：BFS
    public List<List<Integer>> levelOrder(Node root) {
        
    	List<List<Integer>> result = new ArrayList<>();
    	if(root == null)
    		return result;
    	
    	LinkedList<Node> queue = new LinkedList<>();
    	queue.offer(root);
    	
    	while(!queue.isEmpty()) {
    		List<Integer> level = new ArrayList<>();
    		for(int size = queue.size(); size > 0; size--) {
    			Node node = queue.poll();
    			level.add(node.val);
    			if(node.children != null && !node.children.isEmpty())
    				queue.addAll(node.children);
    		}
    		result.add(level);
    	}
    	
    	return result;
    }
	
    //方法二：DFS
    public List<List<Integer>> levelOrder2(Node root) {
    	List<List<Integer>> result = new ArrayList<>();
    	dfs(root, result, 0);
    	return result; 
    }
    
    private void dfs(Node node, List<List<Integer>> result, int level) {
    	if(node == null)
    		return;
    	
    	if(result.size() == level) {
    		List<Integer> temp = new ArrayList<>();
    		temp.add(node.val);
    		result.add(temp);
    	}else {
    		result.get(level).add(node.val);
    	}
    	
    	if(node.children != null ) {
    		for(Node n : node.children)
    			dfs(n, result, level + 1);
    	}
    }
}
